﻿/*
题目: 四数之和

给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] （若两个四元组元素一一对应，则认为两个四元组重复）：

0 <= a, b, c, d < n
a、b、c 和 d 互不相同
nums[a] + nums[b] + nums[c] + nums[d] == target
你可以按 任意顺序 返回答案 。

https://leetcode.cn/problems/4sum/description/
*/

#include <iostream>
#include <random>
#include <string>
#include <vector>
#include <list>
#include "TreeNode.hpp"
#include "ListNode.hpp"
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <functional>

using namespace std;

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        vector<vector<int>> res;
        int n = nums.size();

        ::sort(nums.begin(), nums.end());

        for (int i = 0; i < n - 3; i++) {
            long long sum = nums[i];
            if (i > 0 && nums[i] == nums[i - 1])    continue;

            for (int j = i + 1; j < n - 2; j++) {
                sum = (long long)nums[i] + nums[j];
                if ((j > i + 1 && nums[j] == nums[j - 1]))  continue;

                // 再使用双指针
                int k = j + 1, z = n - 1;
                while (k < z) {
                    sum = (long long)nums[i] + nums[j] + nums[k] + nums[z];
                    if (k > j + 1 && nums[k] == nums[k - 1]) {
                        k++;
                        continue;
                    }
                    if (z < n - 1 && nums[z] == nums[z + 1]) {
                        z--;
                        continue;
                    }

                    if (sum == target) {
                        res.push_back({ nums[i], nums[j], nums[k], nums[z] });
                        k++;
                        z--;
                    }
                    else if (sum < target) {
                        k++;
                    }
                    else if (sum > target) {
                        z--;
                    }
                }
            }
        }

        return res;
    }
};